package com.leetcode.listnode.demo6;

/**
 * @Author Zan
 * @Create 2024/5/13 16:42
 * @ClassName: Test
 * @Description : https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/   面试题 02.07. 链表相交
 */
public class Test {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 6, 3, 4, 5, 6};
//        int[] arr = new int[]{7,7,7,7};
        ListNode listNode = initLinkedList(arr);
        Solution solution = new Solution();
        int size = solution.getSize(listNode);
        System.out.println(size);
    }

    public static ListNode initLinkedList(int[] array) {
        ListNode head = null, current = null;
        for (int i = 0; i < array.length; i++) {
            ListNode newNode = new ListNode(array[i]);
            if (i == 0) { // 头节点
                // 由于head = current，因此当current在变化的时候，head也在变化
                head = newNode;
//                newNode = new Node(array[i]); // 如果在此将newNode重新定义，指向的是不同的堆数据，因此head就只是一个Node普通对象，单节点的链表
                current = newNode;
            } else { // 后面的节点
                current.next = newNode;
                current = newNode;
            }
        }
        return head;
    }
}

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 先获取两个链表的长度大小，让长的那个链表next达到短的链表的长度
        // 然后一起向后找，找到相交的节点
        int sizeA = getSize(headA);
        int sizeB = getSize(headB);

        if (sizeB > sizeA) {
            // B 大于 A 转换为 A > B
            int temp = sizeA;
            sizeA = sizeB;
            sizeB = temp;

            ListNode tempNode = headA;
            headA = headB;
            headB = tempNode;
        }

        // 一直都是headA > headB
        int len = sizeA - sizeB;
        while (len-- > 0) {
            headA = headA.next;
        }

        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;

    }

    public int getSize(ListNode head) {
        int size = 0;
        while (head != null) {
            size++;
            head = head.next;
        }
        return size;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode() {
    }
    public ListNode(int val) {
        this.val = val;
    }
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}